# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional

from BuildTree import *


class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.node = None
        self.nodes = []
        # 中序遍历
        def travel(root:TreeNode):
            if not root: return None
            left = travel(root.left)
            if self.node is not None and root.val < self.node.val:
                self.nodes.append(self.node)
            self.node = root
            if len(self.nodes) == 2:
                self.nodes[1].val, self.nodes[0].val = self.nodes[0].val, self.nodes[1].val
            right = travel(root.right)
        travel(root)
        return root

if __name__ == '__main__':
    s = Solution()
    r = s.recoverTree(build_tree_from_level_order([1,3,null,null,2]))
    ...